• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:
    The present invention provides a method for applying bloom filter on a large data set consisting of key-value pairs, using at least one processor. The method comprising the step of:• partitioning large data-set of key-value pairs into data chunks;• determining Bloom filter Vector and number of segments in the vector for each data chunk;• Encoding all keys of a given Chunk into a Bloom filter vector;• Determining the segment-id of a given key using H (0) hash function;• Encoding Key into a Bloom filter segment with said determined segment-id, using a K-bit array produced by H1,..Hk functions; and• Packing of segments into extent data structures where each extent includes segments of different chunks, but with the same segment-idwherein a single extent filters multiple chunks, depending on a packing factor (the number of segments packed into a single extent).
    公开号:EP3683696A1
    申请号:EP20151789.3
    申请日:2020-01-14
    公开日:2020-07-22
    发明作者:Israel Gold；Yanai NANI ELIYAHU
    申请人:Sqream Technologies Ltd；SQREAM Tech Ltd；
    IPC主号:G06F16-00
    专利说明:
    [0001] A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom_in 1970, that is used to test whether an key is a member of a set. False positive matches are possible, but false negatives are not. The advantage of a Bloom filter over the "conventional" dictionary structures is space efficiency. A Bloom filter needs only a constant number of bits per element, while keeping the false positive rate constant, independent of the size of the elements it is filtering.
    [0002] Bloom filters have been implemented in some very successful and widely deployed systems. For example, Google's Bigtable and Facebok's RocksDB employ Bloom filter to avoid performing disk lookups for non existing data.
    [0003] Recently a Bloom filter variant has been proposed to improve the performance of small hardware tables like processor caches. The blocked bloom filter [BLO], developed by Putze [3] provide a potential solution for the poor memory locality of standard bloom filters. A BLO filter is composed of b smaller and equal size blocks, each managed as a standard bloom filters. In addition, each element is mapped to k bits within a single randomly assigned bloom filter block. Putze [3] claims that BLO filter is more cache efficient by suffering less cache misses.
    [0004] In this document we describe a novel Bloom filter variant for big data sets containing billion of elements. We present of a novel big data bloom filter (BDBF) algorithm that improves the I/O and access times of key search in big tables. References
    [0005] [1] Bloom, Burton H. (1970), "Space/Time Trade-offs in Hash Coding with Allowable Errors", Communications of the ACM, 13 (7): 422-426, doi: 10.1145/362686.362692 [2] Bloom Filter on Wikipedia [3] F. Putze, P. Sanders, and J. Singler. Cache-, hash-, and space-efficient bloom filters. J. Exp. Algorithmics, 14:4:4.4-4:4.18, Jan. 2010.[4] Kaler T., Cache Efficient Bloom Filters for Shared Memory Machines http://tfk.mit.edu/pdf/bloom.pd TECHNICAL FIELD
    [0006] The present invention relates to efficient searching of big data using space-efficient probabilistic data structure like bloom filter. Most applicable usage is searching large key-value stores and/or big database tables. BRIEF SUMMARY
    [0007] The present invention provides a method for applying bloom filter on a large data set consisting of key-value pairs, using at least one processor. The method comprising the step of: partitioning large data-set of key-value pairs into data chunks; determining Bloom filter Vector and number of segments in the vector for each data chunk; Encoding all keys of a given Chunk into a Bloom filter vector; Determining the segment-id of a given key using H (0) hash function; Encoding Key into a Bloom filter segment with said determined segment-id, using a K-bit array produced by H1,..Hk functions; and Packing of segments into extent data structures where each extent includes segments of different chunks, but with the same segment-id. wherein a single extent filters multiple chunks, depending on a packing factor (the number of segments packed into a single extent).
    [0008] According to some embodiments of the present invention the method further comprising the steps of: applying ho function on a given key value to compute segment sj id/index; applying hJ function on key value to compute hash bits vector for the given key-value; testing membership for the given key value of Bloom filter for segment sj , by applying k hash functions.
    [0009] According to some embodiments of the present invention the encoding Key into a Bloom filter segment, is implemented by a Bloom filter with s segments of size Z bytes, and k hash functions, apply key-value insertion by : set all bit of segment sj to false and determine which bit of segment sj are set to true by applying h i(key-value) .
    [0010] According to some embodiments of the present invention the method further comprising the step of determining packing factor (The number of the segments in each extent) is determined by read memory size.
    [0011] According to some embodiments of the present invention the method further comprising the step of maintaining relationships between data chunks, extents and segments by maintaining at least one map table.
    [0012] According to some embodiments of the present invention the extent structure is a bit array structure , ordered by the index.
    [0013] According to some embodiments of the present invention the extent structure filter out multiple chunks in parallel and reduce the number of files required for holding the Bloom filter, guaranteeing that each key is hashed into exactly a single segment requiring only to read and inspect the extents corresponding to that segment-id.8. The method of claim 5 wherein segments can be identified using the segment map using the key, segment id and extent number values.
    [0014] The present invention provides a system for applying bloom filter on large data table of key-value for enabling efficient member testing, said system comprising a non-transitory storage device and one or more processing devices operatively coupled to the storage device on which are stored modules of instruction code executable by the one or more processors : bloom filter module for determining Bloom filter Vector and number of segments in the vector for each data chunk and encoding All Keys of a given,; Chunk into a Bloom filter vector, Determining the segment ID of a given key using H (0) hash function, wherein the large data table of key-value pairs partitioned into data chunks; computation module for encoding Key into Bloom filter segments using a K-bit array produced by H1,..Hk functions; and packing module for packing of segments into extents data structure where each extent includes segments of different chunks with the same id./index. 9. The system of claim 9 further comprising membership test module for performing the steps of : i. applying h0 function on a given key value to compute segment sj id/index; ii. applying hJ function on key value to compute hash bits vector for the given key-value; iii. testing membership for the given key value of Bloom filter for segment sj , by applying k hash functions.
    [0015] According to some embodiments of the present invention the encoding Key into Bloom filter segments, is implemented by for a Given a Bloom filter with s segments of size Z bytes, and k hash functions, apply key-value insertion by : set all bit of segment sj to false and Determine which bit of segment sj are set to true by applying h i(key-value).
    [0016] According to some embodiments of the present invention the packing module further comprising the step of determining packing factor is determined by read memory size.
    [0017] According to some embodiments of the present invention the systems further comprising the mapping module for maintaining relationships between data chunks, extents and segments by maintaining at least one map table.
    [0018] According to some embodiments of the present invention the extent structure is a bit array structure , ordered by the index.
    [0019] According to some embodiments of the present invention the extent structure enable to filter out multiple chunks in parallel and reduce the number of files required for holding the Bloom filter, guaranteeing that each key is hashed into exactly a single segment requiring only to read and inspect the extents corresponding to that segment-id.
    [0020] According to some embodiments of the present invention the segments can be identified using the segment map using the key, segment id and extent number values. BRIEF DESCRIPTION OF THE DRAWINGS
    [0021] The present invention will be more readily understood from the detailed description of embodiments thereof made in conjunction with the accompanying drawings of which: Figure 1 depicts a block diagram, presenting components for applying enhance the bloom filter processing according to some embodiments of the invention. Figure 2 depicts a flow diagram elaborating Generation of Bloom filter segments , according to some embodiments of the present invention. Figure 3 is a flow diagram of Key values encoding of encoding process , according to some embodiments of the invention; Figure 4 is a flow diagram, depicting the processing of packing bloom filter segments, according to some embodiments of the invention. Figure 5 is a flow diagram, depicting the processing of computing segment ID and hash bits vector according to some embodiments of the invention. Figure 6 is a flow diagram of chunk filtering processing according to some embodiments of the invention. Figure 7 illustrates Extent Processing, according to some embodiments of the invention. Figure 8 is a flow diagram of key-value membership test processing , processing according to some embodiments of the invention. Figure 9 is a flow diagram of mapping module processing according to some embodiments of the invention Figure 10 is a visual example of bloom filter segmentation by chunks according to some embodiments of the invention. DETAILED DESCRIPTION
    [0022] Before explaining at least one embodiment of the invention in detail, it is to be understood that the invention is not limited in its application to the details of construction and the arrangement of the components set forth in the following description or illustrated in the drawings. The invention is applicable to other embodiments or of being practiced or carried out in various ways. Also, it is to be understood that the phraseology and terminology employed herein is for the purpose of description and should not be regarded as limiting.
    [0023] Following is a table of definitions of the terms used throughout this application. Term Definition Bloom filter Effective method of indexing large amounts of data by combining hashing and a bit array. The method is used to determine whether a given value is definitely not, or possibly in, a set of values Segmented Bloom filter A bloom filter that is divided into equal size segments, where each segment is managed as a regular bloom filter Segment-id A Segmented Bloom Filter may consists of n segments marked a S1, S2, ..., Sn Segment Si has segment-id of i or index i. Extent A collection of bloom filter segments, where all segments in this collection have the same segment-id Packing factor The number of segments to pack into a single extent Chunk A collection of key-value pairs.BDBF Big Data Bloom Filter algorithm which improves the I/O and access times of data search operations in big tables SBF segments Set of segments that make up a segmented bloom filter
    [0024] The present invention provides a new solution for applying SELECT query for a big dataset consisting of key values pairs. The simple SELECT query, below, exemplify the problem:SELECT * FROM big_table bt WHERE bt.uuid = 'B667B973-2D77-412C-BFA1-85204524AC82'
    [0025] Bloom filter acts as "index like" method; it can filter out key values that we definitely know not to be in big table.
    [0026] Dividing a big table into chunks enables to create a collection of bloom filters which can be easily managed , such that each chunk may be filtered out separately. For more effective chunks filtering , it is suggested according to the present invention to build a Segmented Bloom Filter for each chunk, and pack the segments with the same index into extent data structures. This novel approach facilitates an extent structure having the same size as the original segmented bloom filters which enables to filter out multiple chunks, rather than processing of single chunks as known in prior art.
    [0027] Figure 1 depicts a block diagram, presenting components for applying enhance the bloom filter on big data processing according to some embodiments of the invention. A big data table of key-value pairs is partitioned into chunks. Each chunk key values are processed by segmented bloom filter module 14. At the first stage are generated Bloom filter segments (16), into these segments are encoded key values (18). At the next stage the Bloom filter segments with encoded keys values , are packed into data structure of extents. Each extent only includes segments with the same index; the extent may include some of the segments with the same index or all of them , according to predefined packing factor. The extents are saved in a bit array structure , ordered by their number. To enable efficient data retrieval the extents are mapped to be associated with the segment ID and chunk ID.
    [0028] Figure 2 depicts a flow diagram elaborating the processing of generating of Bloom filter segments , according to some embodiments of the present invention. This processing includes the following steps: Determining Bloom filter Vector and number of segments in the vector (step 162); Encoding All Keys of a given Chunk into a Bloom filter vector (step 164); Determining the segment ID of a given key using H0 hash function (step 166) Encoding Key into Bloom filter segment using a K-bit array produced by H1,..Hk functions (step 168)
    [0029] Figure 3 is a flow diagram of Key values encoding of encoding process , according to some embodiments of the invention. This processing includes the following steps:Given a Bloom filter with s segments of size Z bytes, and k hash functions(182), apply key-value insertion by set all bit of segment sj to false (184), Determine which bit of segment sj are set to true by applying h i(key-value)(186)
    [0030] Figure 4 is a flow diagram, depicting the processing of packing bloom filter segments, according to some embodiments of the invention. This processing includes the following steps: packing of segments into extents (data structure) where each extent include on segments of different chunks with the same id./index (step 202) Determining packing factor (The number of the segments in each extent) for example can be determined by read memory size (packing factor ) (step 204) Packing into a single extent consecutive P segments of the same index according to chunk order (step 206); Generating extent/segment map (step 208);
    [0031] The extent data structure enable to reduce the number of files required for holding the Bloom filter, and improve I/O, by packing multiple segments having the same segment ID into a single extent and save it to disk. For example, a bloom filter for a chunk of size 1MB, may include 16 segments size 64KB each. When using packing factor of 16, each consecutive group of 16 chunks, all SBF segments with segment-id = 1 of the 16 chunks in the group are packed into extent. 1, and all segments with segment-id = 2 for the 16 chunks in the group are packed into extent. 2 and so on, as illustrated in Figure 4. At the end of the packing procedure for each group of 16 chunks we end up with 16 extents with a total size of 16MB. (the same size of 16 classical Bloom filter for corresponding chunks). However, each extent of 1MB can be used for filtering 16 chunks.: Several parameters affect the performance of a Bloom filterchunk size - byte size of a chunk segment size - byte size of a bloom filter segment pack factor - number of segments packed in an extent k - number of hash functions needed to hash a key h 0 - hash function used to compute the segment index for a given key value h 1,,, h k - hash functions for computing the hash bits for a given key value according to some embodiments of the present invention a single extent can filter multiple chunks, depending on a packing factor (the number of segments packed into a single extent), hence this structure of the extent is much more efficient than using the orthogonal Bloom Filter algorithm to filter a single chunk at atme .
    [0032] Figure 5 is a flow diagram, depicting the computation module for processing of computing segment ID and hash bits vector according to some embodiments of the invention. This processing includes the following steps: Applying ho function on key value to compute segment id/index (step 282); Applying hi function on key value to compute hash bits vector for Each key-value (step 284);
    [0033] Figure 6 is a flow diagram of chunk filtering module processing according to some embodiments of the invention.select all big-table extents and for each extent E, determine whether, or not, the chunks represented by E needs to be included in the SELECT by applying extent processing (step 302)
    [0034] Figure 7 illustrates Extent module Processing, according to some embodiments of the invention. This processing includes the following steps: processing the segments stored in that extents. These segments can be identified using the segment map using the key, segment id and extent number values, (step 322) Applying key-value membership test to each segment (step 324)
    [0035] Figure 8 is a flow diagram of key-value membership test module processing, processing according to some embodiments of the invention.Test membership for key value of Bloom filter for segment sj of size Z bytes, by applying k hash functions (step 342)Calculate x key value by applying hi(key-value) (step 344)Check if X bit is true or false in segment (step 346)
    [0036] Figure 9 is a flow diagram of mapping module processing according to some embodiments of the invention. This processing includes the following steps: Maintaining relationships between data chunks, extents and segments by maintaining three map tables (step 222) Maintaining chunk-map table by storing information about data chunks associate given chunk-number to chunk_ file path (step 224) Maintaining extent-map table by storing information about extents; associate a given extent number to extent file path (step 226) Mapping segment table (sbf-map table) by storing information about all segments maintaining the relationship between segments, extents and chunks (step 228)
    [0037] Given a big table containing (key, value) pairs the Map Tables described below maintain the relationship between data chunks, extents and segments. There are three map tables,. Chunk Map Table
    [0038] The chunk-map table stores information about data chunks; it maps a given chunk-number to chunk_file path. chunk-map(chunk-number // unique id per chunkchunk filepath,chunk_size)Extent Map Table
    [0039] The extent-map table stores information about extents; it maps a given extent number to extent file path.
    [0040] The sbf-map table stores information about all segments; it keeps the relationship between segments, extents and chunks.
    [0041] According to some embodiment of the present invention the above map tables are implemented using SQL tables so that they can be queries using SQL as follows:
    [0042] The main benefit of employing a bloom filter for filtering records with a given <key> value is by avoiding reading chunks having no record with the provided <key> value. This can be done efficiently using the BDBF filter as suggested by the present invention.
    [0043] The segmented bloom filtering algorithm according to the present invention guarantees that each key is hashed into exactly a single segment. Accordingly , once the segment id for a given <key> value is computed, there is a need to read all segments, requiring only to inspect the SBF segments corresponding to the segment-id. In other words, it is only required to read and inspect the extents corresponding to that segment-id.
    [0044] This BDBF algorithm filter and minimizes the I/O cost in case of false filtering results. The benefits directly affect the cost of chunk access. this benefit has greater impact when the data chunks are distributed over multiple processor nodes. Membership Testing
    [0045] This section presents the principles of membership testing when using the BDBF filter algorithm. The following paragraph exemplify implementation of SQL SELECT operations of -selecting predicate of the form key=<key-value>. For example,
    [0046] In the following example is shown how the algorithm avoid reading chunks with records not including the predicate key=<key-value>.Compute segment-id and hash bits vector Step (1): compute segment id and hash bits for <key-value>
    [0047] Given Bloom filter with s segments each of seg size bytes, and k hash functions, key value insertion is done as following
    [0048] Step (2): select all big-table extents and for each extent E, determine whether, or not, the chunks represented by E needs to be included in the SELECT. The number of chunks that can be filtered by a single extent is determined by the pack factor (see 003 definitions). Step(2) is implemented as follows
    [0049] Extent processing is performed to all the segments stored in that extents. These segments can be identified using the segment map using the key, segment id and extent number values, as implemented by the BDBF_PROCESS_EXTENT function.
    [0050] Figure 10 is a visual example of bloom filter segmentation by chunks according to some embodiments of the invention.
    [0051] In the above description, an embodiment is an example or implementation of the invention. The various appearances of "one embodiment", "an embodiment" or "some embodiments" do not necessarily all refer to the same embodiments.
    [0052] Although various features of the invention may be described in the context of a single embodiment, the features may also be provided separately or in any suitable combination. Conversely, although the invention may be described herein in the context of separate embodiments for clarity, the invention may also be implemented in a single embodiment.
    [0053] Furthermore, it is to be understood that the invention can be carried out or practiced in various ways and that the invention can be implemented in embodiments other than the ones outlined in the description above.
    [0054] The invention is not limited to those diagrams or to the corresponding descriptions. For example, flow need not move through each illustrated box or state, or in exactly the same order as illustrated and described.
    [0055] Meanings of technical and scientific terms used herein are to be commonly understood as by one of ordinary skill in the art to which the invention belongs, unless otherwise defined.
    [0056] The apparatus of the present invention may include, according to certain embodiments of the invention, machine readable memory containing or otherwise storing a program of instructions which, when executed by the machine, implements some or all of the apparatus, methods, features and functionalities of the invention shown and described herein. Alternatively or in addition, the apparatus of the present invention may include, according to certain embodiments of the invention, a program as above which may be written in any conventional programming language, and optionally a machine for executing the program such as but not limited to a general purpose computer which may optionally be configured or activated in accordance with the teachings of the present invention. Any of the teachings incorporated herein may wherever suitable operate on signals representative of physical objects or substances.
    [0057] Unless specifically stated otherwise, as apparent from the following discussions, it is appreciated that throughout the specification discussions, utilizing terms such as, "processing", "computing", "estimating", "selecting", "ranking", "grading", "calculating", "determining", "generating", "reassessing", "classifying", "generating", "producing", "stereo-matching", "registering", "detecting", "associating", "superimposing", "obtaining" or the like, refer to the action and/or processes of a computer or computing system, or processor or similar electronic computing device, that manipulate and/or transform data represented as physical, such as electronic, quantities within the computing system's registers and/or memories, into other data similarly represented as physical quantities within the computing system's memories, registers or other such information storage, transmission or display devices. The term "computer" should be broadly construed to cover any kind of electronic device with data processing capabilities, including, by way of nonlimiting example, personal computers, servers, computing system, communication devices, processors (e.g. digital signal processor (DSP), microcontrollers, field programmable gate array (FPGA), application specific integrated circuit (ASIC), etc.) and other electronic computing devices.
    [0058] The present invention may be described, merely for clarity, in terms of terminology specific to particular programming languages, operating systems, browsers, system versions, individual products, and the like. It will be appreciated that this terminology is intended to convey general principles of operation clearly and briefly, by way of example, and is not intended to limit the scope of the invention to any particular programming language, operating system, browser, system version, or individual product.
    [0059] It is appreciated that software components of the present invention including programs and data may, if desired, be implemented in ROM (read only memory) form including CD-ROMs, EPROMs and EEPROMs, or may be stored in any other suitable typically non-transitory computer-readable medium such as but not limited to disks of various kinds, cards of various kinds and RAMs. Components described herein as software may, alternatively, be implemented wholly or partly in hardware, if desired, using conventional techniques. Conversely, components described herein as hardware may, alternatively, be implemented wholly or partly in software, if desired, using conventional techniques.
    [0060] Included in the scope of the present invention, inter alia, are electromagnetic signals carrying computer-readable instructions for performing any or all of the steps of any of the methods shown and described herein, in any suitable order; machine-readable instructions for performing any or all of the steps of any of the methods shown and described herein, in any suitable order; program storage devices readable by machine, tangibly embodying a program of instructions executable by the machine to perform any or all of the steps of any of the methods shown and described herein, in any suitable order; a computer program product comprising a computer useable medium having computer readable program code, such as executable code, having embodied therein, and/or including computer readable program code for performing, any or all of the steps of any of the methods shown and described herein, in any suitable order; any technical effects brought about by any or all of the steps of any of the methods shown and described herein, when performed in any suitable order; any suitable apparatus or device or combination of such, programmed to perform, alone or in combination, any or all of the steps of any of the methods shown and described herein, in any suitable order; electronic devices each including a processor and a cooperating input device and/or output device and operative to perform in software any steps shown and described herein; information storage devices or physical records, such as disks or hard drives, causing a computer or other device to be configured so as to carry out any or all of the steps of any of the methods shown and described herein, in any suitable order; a program pre-stored e.g. in memory or on an information network such as the Internet, before or after being downloaded, which embodies any or all of the steps of any of the methods shown and described herein, in any suitable order, and the method of uploading or downloading such, and a system including server/s and/or client/s for using such; and hardware which performs any or all of the steps of any of the methods shown and described herein, in any suitable order, either alone or in conjunction with software. Any computer-readable or machine-readable media described herein is intended to include non-transitory computer- or machine-readable media.
    [0061] Any computations or other forms of analysis described herein may be performed by a suitable computerized method. Any step described herein may be computer-implemented. The invention shown and described herein may include (a) using a computerized method to identify a solution to any of the problems or for any of the objectives described herein, the solution optionally include at least one of a decision, an action, a product, a service or any other information described herein that impacts, in a positive manner, a problem or objectives described herein; and (b) outputting the solution.
    [0062] The scope of the present invention is not limited to structures and functions specifically described herein and is also intended to include devices which have the capacity to yield a structure, or perform a function, described herein, such that even though users of the device may not use the capacity, they are, if they so desire, able to modify the device to obtain the structure or function.
    [0063] Features of the present invention which are described in the context of separate embodiments may also be provided in combination in a single embodiment.
    [0064] For example, a system embodiment is intended to include a corresponding process embodiment. Also, each system embodiment is intended to include a server-centered "view" or client centered "view", or "view" from any other node of the system, of the entire functionality of the system, computer-readable medium, apparatus, including only those functionalities performed at that server or client or node.
    权利要求:
    Claims (16)
    [0001] A method for applying bloom filter on a large data set consisting of key-value pairs, using at least one processor, the method comprising the step of:
    • partitioning large data-set of key-value pairs into data chunks;
    • determining Bloom filter Vector and number of segments in the vector for each data chunk;
    • Encoding all keys of a given Chunk into a Bloom filter vector;
    • Determining the segment-id of a given key using H (0) hash function;
    • Encoding Key into a Bloom filter segment with said determined segment-id, using a K-bit array produced by H1,..Hk functions; and
    • Packing of segments into extent data structures where each extent includes segments of different chunks, but with the same segment-id.wherein a single extent filters multiple chunks, depending on the number of segments packed into a single extent(packing factor).
    [0002] The method of claim 1 further comprising the steps of :
    - applying ho function on a given key value to compute segment sj id/index;
    - applying hJ function on key value to compute hash bits vector for the given key-value;
    - testing membership for the given key value of Bloom filter for segment sj , by applying k hash functions.
    [0003] The method of claim 1 wherein Encoding Key into a Bloom filter segment, is implemented by a Bloom filter with s segments of size Z bytes, and k hash functions, apply key-value insertion by : set all bit of segment sj to false and determine which bit of segment sj are set to true by applying h i(key-value).
    [0004] The method of claim 1 further comprising the step of determining packing factor (The number of the segments in each extent) is determined by read memory size.
    [0005] The method of claim 1 further comprising the step of maintaining relationships between data chunks, extents and segments by maintaining at least one map table.
    [0006] The method of claim 1 wherein the extent structure is a bit array structure, ordered by the index.
    [0007] The method of claim 1 wherein the extent structure filter out multiple chunks in parallel and reduce the number of files required for holding the Bloom filter, guaranteeing that each key is hashed into exactly a single segment requiring only to read and inspect the extents corresponding to that segment-id.
    [0008] The method of claim 5 wherein segments can be identified using the segment map using the key, segment id and extent number values.
    [0009] A system for applying bloom filter on large data table of key-value for enabling efficient member testing , said system comprising a non-transitory storage device and one or more processing devices operatively coupled to the storage device on which are stored modules of instruction code executable by the one or more processors :
    • bloom filter module for determining Bloom filter Vector and number of segments in the vector for each data chunk and encoding All Keys of a given,; Chunk into a Bloom filter vector, Determining the segment ID of a given key using H (0) hash function, wherein the large data table of key-value pairs partitioned into data chunks;
    • computation module for encoding Key into Bloom filter segments using a K-bit array produced by H1,..Hk functions; and
    • packing module for packing of segments into extents data structure where each extent includes segments of different chunks with the same id./index.
    [0010] The system of claim 9 further comprising membership test module for performing the steps of :
    i. applying ho function on a given key value to compute segment sj id/index;
    ii. applying hJ function on key value to compute hash bits vector for the given key-value;
    iii. testing membership for the given key value of Bloom filter for segment sj , by applying k hash functions.
    [0011] The system of claim 9 wherein Encoding Key into Bloom filter segments, is implemented by for a Given a Bloom filter with s segments of size Z bytes, and k hash functions, apply key-value insertion by : set all bit of segment sj to false and Determine which bit of segment sj are set to true by applying h i(key-value).
    [0012] The system of claim 9 wherein the packing module further comprising the step of determining packing factor is determined by read memory size.
    [0013] The system of claim 9 further comprising the mapping module for maintaining relationships between data chunks, extents and segments by maintaining at least one map table.
    [0014] The system of claim 9 wherein the extent structure is a bit array structure , ordered by the index.
    [0015] The system of claim 9 wherein the extent structure enable to filter out multiple chunks in parallel and reduce the number of files required for holding the Bloom filter, guaranteeing that each key is hashed into exactly a single segment requiring only to read and inspect the extents corresponding to that segment-id.
    [0016] The systems of claim 9 wherein segments can be identified using the segment map using the key, segment id and extent number values.
    类似技术:
    公开号 | 公开日 | 专利标题
    US20180095986A1|2018-04-05|Creation of synthetic backups within deduplication storage system by a backup application
    Kraska et al.2018|The case for learned index structures
    Raju et al.2017|Pebblesdb: Building key-value stores using fragmented log-structured merge trees
    Wang et al.2014|Oblivious data structures
    US10162598B2|2018-12-25|Flash optimized columnar data layout and data access algorithms for big data query engines
    AU2017202873B2|2019-04-11|Efficient query processing using histograms in a columnar database
    US9727573B1|2017-08-08|Out-of core similarity matching
    Fu et al.2015|Design tradeoffs for data deduplication performance in backup workloads
    US9367574B2|2016-06-14|Efficient query processing in columnar databases using bloom filters
    US20200050968A1|2020-02-13|Interactive interfaces for machine learning model evaluations
    CA2953959C|2021-02-02|Feature processing recipes for machine learning
    US9081809B2|2015-07-14|Scalable deduplication system with small blocks
    JP6356675B2|2018-07-11|Aggregation / grouping operation: Hardware implementation of hash table method
    US10761758B2|2020-09-01|Data aware deduplication object storage |
    US20190122136A1|2019-04-25|Feature processing tradeoff management
    US10963810B2|2021-03-30|Efficient duplicate detection for machine learning data sets
    Holley et al.2016|Bloom Filter Trie: an alignment-free and reference-free data structure for pan-genome storage
    US9594524B2|2017-03-14|System and method for distributed computing in non-volatile memory
    US9672474B2|2017-06-06|Concurrent binning of machine learning data
    US9158843B1|2015-10-13|Addressing mechanism for data at world wide scale
    JP6507245B2|2019-04-24|Database search system and database search method
    US10318882B2|2019-06-11|Optimized training of linear machine learning models
    US10108633B2|2018-10-23|Using a distributed prime data sieve for efficient lossless reduction, search, and retrieval of data
    US20140337315A1|2014-11-13|Method and system for storing, organizing and processing data in a relational database
    JP2957703B2|1999-10-06|Method and memory structure for storing and retrieving data
    同族专利:
    公开号 | 公开日
    US20200226112A1|2020-07-16|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    法律状态:
    2020-06-19| PUAI| Public reference made under article 153(3) epc to a published international application that has entered the european phase|Free format text: ORIGINAL CODE: 0009012 |
    2020-06-19| STAA| Information on the status of an ep patent application or granted ep patent|Free format text: STATUS: THE APPLICATION HAS BEEN PUBLISHED |
    2020-07-22| AX| Request for extension of the european patent|Extension state: BA ME |
    2020-07-22| AK| Designated contracting states|Kind code of ref document: A1 Designated state(s): AL AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HR HU IE IS IT LI LT LU LV MC MK MT NL NO PL PT RO RS SE SI SK SM TR |
    2021-01-29| STAA| Information on the status of an ep patent application or granted ep patent|Free format text: STATUS: REQUEST FOR EXAMINATION WAS MADE |
    2021-03-03| 17P| Request for examination filed|Effective date: 20210122 |
    2021-03-03| RBV| Designated contracting states (corrected)|Designated state(s): AL AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HR HU IE IS IT LI LT LU LV MC MK MT NL NO PL PT RO RS SE SI SK SM TR |
    2021-12-17| STAA| Information on the status of an ep patent application or granted ep patent|Free format text: STATUS: EXAMINATION IS IN PROGRESS |
    2022-01-19| 17Q| First examination report despatched|Effective date: 20211220 |
    优先权:
    申请号 | 申请日 | 专利标题
    [返回顶部]